/LMAR=0/FONT#0=NGR25/FONT#1=FIX25/FONT#2=CLAR30



␈↓ α,␈↓α␈α?␈α?␈α?␈αλA Recursive Paged Virtual Memory
␈↓ α,␈↓␈α?␈α?␈α?␈α?␈α?␈α?␈α?␈α∩Larry Masinter

␈↓ α,␈↓␈α?␈α?␈α?␈α?␈α?␈α?␈α?␈α:11/2/74












␈↓ α,␈↓αAbstract
␈↓ α,␈↓This␈α⊂virtual␈α⊂memory␈α⊃scheme␈α⊂is␈α⊂an␈α⊂attempt␈α⊃to␈α⊂provide␈α⊂a␈α⊂virtually␈α⊃unlimited␈α⊂address
␈↓ α,␈↓space␈α
while␈α
allowing␈α
programs␈α
to␈αuse␈α
relatively␈α
short␈α
addresses␈α
for␈α
local␈αreferences.␈α
A
␈↓ α,␈↓basic address mapping scheme for variable length addresses is described.


␈↓ α,␈↓αDisclaimer
␈↓ α,␈↓The␈αideas␈αpresented␈αherein␈αare␈αacknowledged␈αto␈αbe␈αhalf-baked.␈αFurther,␈αthis␈αdoes␈αnot
␈↓ α,␈↓begin␈α∃to␈α∀satisfy␈α∃the␈α∀specification␈α∃of␈α∀the␈α∃assignment.␈α∀ However,␈α∃I␈α∀think␈α∃it␈α∃is␈α∀an
␈↓ α,␈↓interesting idea.


␈↓ α,␈↓αHardware
␈↓ α,␈↓The␈α⊂scheme␈α∂is␈α⊂described␈α∂in␈α⊂terms␈α⊂of␈α∂interpreting␈α⊂instructions␈α∂and␈α⊂addresses␈α⊂on␈α∂an
␈↓ α,␈↓unspecified␈α
16␈αbit␈α
machine␈αwith␈α
up␈αto␈α
64K␈α(2↑16)␈α
words␈αof␈α
main␈αmemory.␈α
 Details␈αfor␈α
a
␈↓ α,␈↓particular machine have not been worked out.


␈↓ α,␈↓αMemory structure
␈↓ α,␈↓The␈α
memory␈α
is␈α
structured␈α
as␈α
a␈α
256-ary␈α
tree;␈α
each␈α
of␈α
the␈α
nodes␈α
is␈α
a␈α
page␈α
table,␈αand
␈↓ α,␈↓each␈α∞of␈α
the␈α∞leaves␈α∞is␈α
a␈α∞page␈α
of␈α∞data␈α∞or␈α
instructions.␈α∞A␈α
virtual␈α∞address␈α∞is␈α
completely
␈↓ α,␈↓specified␈αby␈αa␈αsequence␈αof␈αindices␈αfrom␈αthe␈αroot␈αnode.␈αThe␈αfirst␈αbyte␈αgives␈αthe␈αindex
␈↓ α,␈↓in␈αthe␈αroot␈αpage␈αtable.␈αThis␈αentry␈αcontains␈αan␈αindication␈αthat␈αit␈αis␈αeither␈αa␈αpointer␈αto␈αa
␈↓ α,␈↓data␈α∪page␈α∩or␈α∪to␈α∩another␈α∪page␈α∩table.␈α∪If␈α∪it␈α∩points␈α∪to␈α∩a␈α∪data␈α∩page,␈α∪the␈α∪next␈α∩byte
␈↓ α,␈↓determines␈α∂the␈α∂word␈α∂number␈α∂within␈α∂that␈α⊂data␈α∂page;␈α∂if␈α∂a␈α∂page␈α∂table,␈α∂the␈α⊂process␈α∂is
␈↓ α,␈↓iterated.␈α Looking␈α
from␈αthe␈α
bottom␈αup,␈α
each␈αpage␈α
(either␈αdata␈α
or␈αpage␈α
table,␈αexcept␈α
for
␈↓ α,␈↓the␈α↔root)␈α↔has␈α↔a␈α↔PARENT␈α↔page␈α↔table,␈α↔and␈α↔a␈α↔page␈α↔number␈α↔(within␈α↔its␈α↔parent).
␈↓ α,␈↓Alternatively,␈α
a␈αpage␈α
table␈α
entry␈αmay␈α
contain␈α
an␈αindication␈α
that␈α
the␈αpage␈α
is␈α
not␈αin␈α
core,
␈↓ α,␈↓and␈αthe␈αhigh␈αorder␈αbits␈αof␈αits␈αdisk␈αaddress.␈αThe␈αlow␈αorder␈αbits␈αare␈αdetermined␈αby␈αthe
␈↓ α,␈↓page number.



␈↓ α,␈↓Additionally,␈α⊃each␈α⊃page␈α⊃in␈α∩the␈α⊃virtual␈α⊃memory␈α⊃has␈α∩a␈α⊃unique␈α⊃disk␈α⊃address.␈α∩ As␈α⊃the
␈↓ α,␈↓physical␈αsize␈αof␈αthe␈αdisk␈αis␈α?,␈αthis␈αlimits␈αthe␈αvirtual␈αmemory␈αsize␈αto␈αbe␈αthat␈αof␈αthe␈αdisk.
␈↓ α,␈↓The␈α⊂disk␈α⊂addresses␈α⊂of␈α⊂those␈α⊂pages␈α⊃which␈α⊂are␈α⊂currently␈α⊂in␈α⊂core␈α⊂is␈α⊂maintained␈α⊃in␈α⊂a
␈↓ α,␈↓separate table, the Known Page Table.


␈↓ α,␈↓αData Structures
␈↓ α,␈↓Each␈αpage␈α
is␈αeither␈α
a␈αdata␈αpage␈α
containing␈α256␈α
words␈α(512␈α
8-bit␈αbytes)␈αof␈α
instructions
␈↓ α,␈↓or␈αdata,␈αor␈αelse␈αa␈αpage␈αtable,␈αcontaining␈α256␈αpage␈αtable␈αentries␈α(PTE's).␈αThe␈αformat␈αof
␈↓ α,␈↓a PTE is:
␈↓ α,␈↓A Recursive Paged Virtual Memory␈↓ 
l2



␈↓ α,␈↓↓bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
␈↓ α,␈↓↓    +---------------+---------------+
␈↓ α,␈↓↓    |0| high order bits disk address|  page not in core
␈↓ α,␈↓↓    +---------------+---------------+



␈↓ α,␈↓↓bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
␈↓ α,␈↓↓    +---------------+---------------+
␈↓ α,␈↓↓    |1|1| reserved  | RMP           |   data page
␈↓ α,␈↓↓    +---------------+---------------+



␈↓ α,␈↓↓bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
␈↓ α,␈↓↓    +---------------+---------------+
␈↓ α,␈↓↓    |1|0| reserved  | RMP           |    pointer to page table
␈↓ α,␈↓↓    +---------------+---------------+


␈↓ α,␈↓↓notes:
␈↓ α,␈↓↓(1) a few disk addresses are reserved for special meaning; e.g.
␈↓ α,␈↓↓  zeros:        pseudo data page of all zeros.
␈↓ α,␈↓↓  extend:       this turns in to a page table, each entry of
␈↓ α,␈↓↓                which is a "zeros" entry except the first, which
␈↓ α,␈↓↓                contains an "extend". Good for stacks.

␈↓ α,␈↓↓(2) RMP: Real Memory Page. A page number in real memory (0-255).

␈↓ α,␈↓↓(3) bit 0 is the "in core" bit. A reference thru an entry with
␈↓ α,␈↓↓    this bit off will fault.

␈↓ α,␈↓↓(4) If in core, bit 1 is the "data page" bit; if on, the RMP pointed
␈↓ α,␈↓↓    to contains data; otherwise it contains a page table.

␈↓ α,␈↓↓(5) The low order bit of the disk address is determined by
␈↓ α,␈↓↓    the low order bit of the page number in its parent.

␈↓ α,␈↓↓(6) Bits 2-7 will contain protection information


␈↓ α,␈↓αKnown Page Table
␈↓ α,␈↓The␈αmain␈αother␈αdata␈αstructure␈αused␈αin␈αthe␈αmemory␈αscheme␈αis␈αa␈α(fixed)␈αtwo␈αpage␈αarray
␈↓ α,␈↓called␈α⊃the␈α⊃Known␈α⊃Page␈α⊃Table.␈α∩It␈α⊃contains␈α⊃additional␈α⊃information␈α⊃about␈α∩those␈α⊃pages
␈↓ α,␈↓which␈αare␈α
in␈αcore.␈α
The␈αfirst␈α
part␈αof␈α
the␈αKPT␈α
contains␈αthe␈α
real␈αdisk␈α
address␈αof␈αthe␈α
page.
␈↓ α,␈↓The second part of the KPT contains the parent information. PARENT(rmp) is either:
␈↓ α,␈↓A Recursive Paged Virtual Memory␈↓ 
l3


␈↓ α,␈↓↓bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
␈↓ α,␈↓↓    +---------------+---------------+
␈↓ α,␈↓↓    |0| high order bits disk addr.  |   parent not in core
␈↓ α,␈↓↓    +---------------+---------------+
␈↓ α,␈↓↓bit: 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
␈↓ α,␈↓↓    +---------------+---------------+
␈↓ α,␈↓↓    |1| pn          | RMP           |   parent in core; RMP
␈↓ α,␈↓↓    +---------------+---------------+   is its real address;
␈↓ α,␈↓↓                                        pn is high order bits of
␈↓ α,␈↓↓                                        page number within parent.


␈↓ α,␈↓αRegisters
␈↓ α,␈↓As␈α
the␈α
depth␈α
of␈α
the␈α
virtual␈α
memory␈α
tree␈α
increases,␈α
addresses␈α
relative␈α
to␈α
the␈α
root␈α
of
␈↓ α,␈↓the␈α∞tree␈α∞grow␈α
longer.␈α∞ Thus,␈α∞4␈α∞address␈α
"registers"␈α∞are␈α∞provided.␈α∞Memory␈α
references
␈↓ α,␈↓are␈αalways␈αmade␈αwith␈αrespect␈αto␈α
one␈αof␈αthese␈αregisters.␈αEach␈αregister␈αcontains␈α
an␈α8-
␈↓ α,␈↓bit␈αreal␈αmemory␈α
page␈αnumber.␈αThe␈αfour␈α
pages␈αreferred␈αto␈αin␈α
the␈αregisters␈αare␈αall␈α
page
␈↓ α,␈↓tables; and all are considered locked into core until the values of the registers change.
␈↓ α,␈↓↓        SP0:    stack
␈↓ α,␈↓↓        PC0:    program counter
␈↓ α,␈↓↓        DP0:    data
␈↓ α,␈↓↓        GP0:    general register

␈↓ α,␈↓Each␈α∩opcode␈α∩specifies␈α∩one␈α∩of␈α∩these␈α∪address␈α∩registers␈α∩as␈α∩a␈α∩context␈α∩in␈α∪which␈α∩the
␈↓ α,␈↓following␈α
bytes␈αare␈α
interpreted.␈α
 SP␈αand␈α
PC␈αeach␈α
have␈α
two␈αbyte␈α
extensions:␈α
SP1␈αand
␈↓ α,␈↓PC1␈αare␈αthe␈αreal␈αmemory␈αpages␈α(RMPs)␈αof␈αthe␈αcurrent␈αstack␈αand␈αprogram␈αcounter,␈α
SP2
␈↓ α,␈↓and␈α
PC2␈α
are␈α
offsets␈α
therein.␈α
PCX␈α
is␈α
a␈α
one-bit␈α
odd␈α
byte␈α
indicator.␈α
Thus,␈α
for␈α
example,␈α
the
␈↓ α,␈↓16␈α
bit␈α
quantity␈α<SP1,SP2>␈α
is␈α
the␈αreal␈α
memory␈α
address␈α(RMA)␈α
of␈α
the␈αtop␈α
of␈α
the␈αstack.
␈↓ α,␈↓Stored␈αin␈αthe␈αmemory␈αare␈αthe␈αvirtual␈αaddresses␈αof␈αDP0,␈αPC1,␈αand␈αSP1␈αwith␈αrespect␈αto
␈↓ α,␈↓the root.


␈↓ α,␈↓αInstructions
␈↓ α,␈↓An␈αinstruction␈αconsists␈αof␈αa␈α1␈αbyte␈αopcode,␈αfollowed␈αby␈αan␈αarbitrary␈αnumber␈αof␈αbytes
␈↓ α,␈↓of␈α⊂address.␈α⊂Each␈α∂instruction␈α⊂has␈α⊂addressing␈α⊂mode(s).␈α∂ An␈α⊂addressing␈α⊂mode␈α⊂is␈α∂either
␈↓ α,␈↓relative␈αto␈αa␈αparticular␈αregister,␈αor␈αa␈αmode␈αlocal␈αto␈αSP␈αor␈αPC.␈αVarious␈α
instructions␈αare
␈↓ α,␈↓presented below:
␈↓ α,␈↓A Recursive Paged Virtual Memory␈↓ 
l4



␈↓ α,␈↓↓ Instruction    Mode    Interpretation


␈↓ α,␈↓↓          Standard Instructions

␈↓ α,␈↓↓  JUMP b1...bn  PC0     Fetch [PC0; b1,...,bn] as next opcode;
␈↓ α,␈↓↓                        reset PC0 to RMP of last page table found,
␈↓ α,␈↓↓                        PC1 to last page, and PC2 to bn; set PCX
␈↓ α,␈↓↓                        to 0. (note that n ≥ 2). Might also provide
␈↓ α,␈↓↓                        a JUMP relative to ROOT.

␈↓ α,␈↓↓  LJUMP b       PC      Reset PC2 to b; set PCX to 0.
␈↓ α,␈↓↓                        (note that one cannot jump to an odd byte)
␈↓ α,␈↓↓  PUSH b1...bn  SP,DP0  Fetch [DP0; b1, b2, ... , bn]; store at
␈↓ α,␈↓↓                        RMA <SP1,SP2>; decrement SP (see below).

␈↓ α,␈↓↓  POP b1...bn   SP,DP0  Increment SP (see below) and store the
␈↓ α,␈↓↓                        contents of <SP1,SP2> at [DP0; b1,...,bn]

␈↓ α,␈↓↓  STKNTH n      SP      Push SP+n onto stack. (note that stacks
␈↓ α,␈↓↓                        grow from large addresses to small; this
␈↓ α,␈↓↓                        is so that indirect addressing off the stack
␈↓ α,␈↓↓                        can work)

␈↓ α,␈↓↓  ADD, SUB, etc SP   single byte instructions which work on the top
␈↓ α,␈↓↓                     of the stack.

␈↓ α,␈↓↓        Register manipulations

␈↓ α,␈↓↓ SETSP b1...bn  DP0,SP  Reset SP (works like JUMP).

␈↓ α,␈↓↓ UPDP           DP      Set DP0 to its parent.

␈↓ α,␈↓↓ DOWNDP n               Set DP0 to its n'th entry.


␈↓ α,␈↓αMap Manipulation
␈↓ α,␈↓Instructions␈α
are␈α∞provided␈α
to␈α∞manipulate␈α
the␈α∞address␈α
space:␈α∞the␈α
main␈α∞operation␈α
would
␈↓ α,␈↓be␈α∂to␈α∂reset␈α∂page␈α∂n␈α∞in␈α∂DP0␈α∂to␈α∂contain␈α∂(zeros,␈α∞extend,␈α∂empty,␈α∂a␈α∂copy␈α∂of␈α∂some␈α∞other
␈↓ α,␈↓page). Alternatively, provisions for moving one PTE to another location are provided.
␈↓ α,␈↓A Recursive Paged Virtual Memory␈↓ 
l5


␈↓ α,␈↓αIncrementing and Decrementing
␈↓ α,␈↓When␈αthe␈αvirtual␈αaddress␈αspace␈αis␈αnot␈αlinear,␈αthe␈αconventional␈αconcept␈αof␈α"next␈αword"
␈↓ α,␈↓requires␈αsome␈αredefintion␈αwhen␈αat␈αpage␈αboundaries.␈α If␈αat␈αthe␈αlast␈αword␈αof␈αa␈αpage,␈αthe
␈↓ α,␈↓next word can be defined by:
␈↓ α,␈↓↓go␈α⊂up␈α⊂until␈α⊂you␈α⊂are␈α⊂not␈α⊂at␈α⊂the␈α⊂last␈α⊂entry␈α⊂of␈α⊂a␈α⊂PT;␈α⊂increment␈α⊂the␈α⊂page
␈↓ α,␈↓↓number, and then go down the 0 entries until you hit a data page.

␈↓ α,␈↓A similar mechanism can be defined for decrementing a register.


␈↓ α,␈↓αMore Problems and a Few Solutions
␈↓ α,␈↓A␈αpage␈αtable,␈αwhen␈α
on␈αdisk,␈αcontains␈αdisk␈αaddress␈α
PTE's␈αonly.␈αWhen␈αit␈αis␈α
brought␈αinto
␈↓ α,␈↓core,␈α∞the␈α∞Known␈α
Page␈α∞Table␈α∞is␈α
searched␈α∞for␈α∞entries␈α
containing␈α∞its␈α∞daughters;␈α∞if␈α
they
␈↓ α,␈↓are␈αfound,␈αthe␈α
map␈αis␈αupdated␈α
to␈αshow␈αthat␈α
these␈αpages␈αare␈α
in␈αcore.␈αThis␈αmechanism␈α
is
␈↓ α,␈↓necessary if one is to allow non-connected subparts of the tree to be in core.

␈↓ α,␈↓Arbitrary␈α∞address␈α∞arithmetic␈α∂is␈α∞hard,␈α∞since␈α∞addresses␈α∂are␈α∞not␈α∞uniform␈α∞in␈α∂length.␈α∞The
␈↓ α,␈↓main␈αfacilities␈αavailable␈αare␈αindirection␈αoff␈αthe␈αstack.␈αI␈αgave␈αsome␈αthought␈α
to␈αproblems
␈↓ α,␈↓of variable length arithmetic but didn't pursue it.

␈↓ α,␈↓Unfortunately,␈αthe␈αtree␈αmust␈αactually␈αbe␈αa␈αtree␈αand␈αnot␈αan␈αarbitrary␈αgraph;␈αeach␈αpage
␈↓ α,␈↓must have a unique owner.

␈↓ α,␈↓When␈α
a␈α
page␈α
is␈α
swapped␈α
out,␈α
the␈α∞entries␈α
in␈α
its␈α
parent␈α
(if␈α
in␈α
core),␈α
and␈α∞its␈α
immediate
␈↓ α,␈↓descendants (again if in core) need to be marked.


␈↓ α,␈↓αCriticisms
␈↓ α,␈↓The␈αmajor␈αissues␈αof␈αvirtual␈αmemory␈αon␈αsingle␈αuser␈αmachines␈αhave␈αnot␈αbeen␈αaddressed.
␈↓ α,␈↓The␈α
most␈α
important␈αfactor␈α
distinguishing␈α
the␈αsituation␈α
from␈α
multiprocessing␈αsituations␈α
is
␈↓ α,␈↓that,␈α⊂there␈α⊂are␈α⊂no␈α⊂other␈α⊂users␈α⊂waiting␈α⊂to␈α⊂run␈α⊂if␈α⊂a␈α⊂single␈α⊂user␈α⊂blocks.␈α⊃This␈α⊂weighs
␈↓ α,␈↓heavily␈αagainst␈αdemand␈αpage␈αreplacement␈αstrategies.␈αUsing␈αthe␈αprinciple␈αthat␈αprograms
␈↓ α,␈↓tend␈α
to␈αuse␈α
locallized␈αaddressing,␈α
some␈αprinciple␈α
of␈αfetching␈α
the␈αneighbors␈α
of␈α
a␈αdata-
␈↓ α,␈↓page␈αwhen␈αit␈αis␈αfetched␈αis␈αnot␈αunreasonable.␈α Constraints␈αcan␈αalso␈αbe␈αplaced␈αon␈αwhich
␈↓ α,␈↓pages␈αcan␈αbe␈αthrown␈αout.␈α
 In␈αparticular,␈αall␈αincore␈αpages␈α
should␈αhave␈αsome␈αpath␈αto␈α
one
␈↓ α,␈↓of␈α
the␈αPT's␈α
pointed␈α
to␈αby␈α
the␈α
registers␈α(as␈α
those␈α
are␈αthe␈α
only␈α
way␈αof␈α
getting␈α
at␈αa␈α
page
␈↓ α,␈↓in core).